package common

import "fmt"
//字典树
type Trie struct {
	root* TreeNode
}
//树节点
type TreeNode struct {
	num int
	son map[string]*TreeNode
	isEnd bool
}

func (node *TreeNode) GetSon() map[string]*TreeNode {
	return node.son
}

func (node *TreeNode)IsEnd() bool {
	return node.isEnd
}

//字段数构造函数
func NewTrie() *Trie {
	var trie* Trie = new(Trie)
	trie.root = NewTreeNode()
	return trie
}
//树节点构造函数
func NewTreeNode() *TreeNode {
	var node* TreeNode = new(TreeNode)
	node.son = make(map[string]*TreeNode)
	node.num = 1
	node.isEnd = false
	return node
}
//插入一个分支
func (trie Trie) Insert(word string)  {
	if word == "" {
		return
	}
	node := trie.root
	for _,v := range word {
		s := fmt.Sprintf("%c", v)
		sonNode := node.son[s]
		if sonNode == nil {
			sonNode = NewTreeNode()
			node.son[s] = sonNode
		} else {
			sonNode.num++
		}
		node = sonNode
	}
	node.isEnd = true
}
//获取根节点
func (trie Trie) GetRoot() *TreeNode {
	return trie.root
}
//插入一个string
func (trie Trie) InsertStr(words []string)  {
	if len(words) == 0 {
		return
	}
	node := trie.root
	for _,s := range words {
		sonNode := node.son[s]
		if sonNode == nil {
			sonNode = NewTreeNode()
			node.son[s] = sonNode
		} else {
			sonNode.num++
		}
		node = sonNode
	}
	node.isEnd = true
}